package workexp.alg.question;

import org.junit.Test;

import java.util.*;

public class LengthOfLongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        Set<Character> charSet = new HashSet<>();
        Queue<Character> charQueue = new ArrayDeque<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < s.toCharArray().length; i++) {
            Character c = chars[i];
            if(charSet.contains(c)){
                maxLen=maxLen>charSet.size()?maxLen:charSet.size();

                //用一个栈记录需要清楚的字符
                Character tmp = charQueue.poll();
                while (!tmp.equals(c)){
                    charSet.remove(tmp);
                    tmp=charQueue.poll();
                }
            }
            charSet.add(c);
            charQueue.add(c);

        }
        maxLen=maxLen>charSet.size()?maxLen:charSet.size();
        return maxLen;
    }

    //不使用队列的方法
    public int lengthOfLongestSubstring2(String s){
        int maxLen = 0;
        int right=-1;
        int n = s.length();
        Set<Character> charSet = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if(i!=0){
                charSet.remove(s.charAt(i-1));
            }
            while (right+1<n&&!charSet.contains(s.charAt(right+1))){
                charSet.add(s.charAt(right+1));
                right++;
            }
//            maxLen=maxLen>charSet.size()?maxLen:charSet.size();
            maxLen=maxLen>right-i+1?maxLen:right-i+1;
            if((right-i+1)==n){
                break;
            }
        }
        return maxLen;

    }

    @Test
    public void test(){
        String str="abc";
        int result = lengthOfLongestSubstring2(str);
        System.out.println(result);
    }
}
